/*
 *  Merge Sort(Bottom-up)
 *
 *  Promotion tips:
 *  1. cutoff to insertion sort
 *  2. skip merge if a[mid] < a[mid+1]
 *  3. use auxiliary array
 *
 *  Note:
 *  Only tip 1 is used in this version
 */

package algs4.sort;

import java.util.Random;

public class MergeBU
{
    public static void sort(Comparable[] a) {
        int n   = a.length;
        int cnt = 0;
        Comparable[] aux = new Comparable[n];
        for (int sz = 1; sz < n; sz *= 2, cnt++) {
            int lo;
            if (cnt % 2 == 0) {
                for (lo = 0; lo + sz < n ; lo += sz * 2)
                    merge(a, aux, lo, lo + sz - 1, Math.min(lo + 2 * sz - 1, n - 1));
                if (lo < n)
                    System.arraycopy(a, lo, aux, lo, n - lo);
            } else {
                for (lo = 0; lo + sz < n ; lo += sz * 2)
                    merge(aux, a, lo, lo + sz - 1, Math.min(lo + 2 * sz - 1, n - 1));
                if (lo < n)
                    System.arraycopy(aux, lo, a, lo, n - lo);
            }
        }
        if (cnt % 2 == 1)
            System.arraycopy(aux, 0, a, 0, n);
    }

    private static void merge(Comparable[] src, Comparable[] dst, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)                      dst[k] = src[j++];
            else if (j > hi)                       dst[k] = src[i++];
            else if (src[i].compareTo(src[j]) < 0) dst[k] = src[i++];
            else                                   dst[k] = src[j++];
        }
    }

    private static void show(Comparable[] a) {
        for (Comparable i : a)
            System.out.print(i + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        if (args.length != 1) {
            System.out.println("Usage: Command N");
            System.exit(1);
        }
        int n = Integer.parseInt(args[0]);;

        // Build random array of integer
        Integer[] a   = new Integer[n];
        Random random = new Random(System.currentTimeMillis());
        for (int i = 0; i < n; i++)
            a[i] = random.nextInt(n);

        System.out.print("BF: "); show(a);
        sort(a);
        System.out.print("AF: "); show(a);
    }
}
